package com.wingsboat.sort;

import java.util.Arrays;

/**
 * @author wangzhong
 * @description: 归并排序
 * @date 2024/7/21 10:34
 */
public class MergeSort {
    private MergeSort(){}


    public static void main(String[] args) {
        int[] arr = {5,2,7,0,8,6,3,1,2};
        int[] a = {2,5};
        int[] b = {3,7};
        int[] c = {2,5,3,7};

        MergeSort.sort(c);
        for (int i : c) {
            System.out.println(i);
        }
    }


    public static void sort(int[] arr){
        sort(0,arr.length-1,arr);
    }

    private static void sort(int l,int r,int[] arr){
        if(l==r) return;
        int mid = (l+r)/2+1;
        sort(l,mid-1,arr);
        sort(mid,r,arr);
        mergeArr(l,mid,r,arr);
    }

    public static int[] mergeArr(int[] a,int[] b){
        int i = 0;
        int j =0;
        int index = 0;
        int[] result = new int[a.length+b.length];
        while(i<a.length || j<b.length){
            if(i==a.length && j<b.length){
                result[index] = b[j];
                j+=1;
            }else if(j==b.length && i<a.length){
                result[index] = a[i];
                i+=1;
            }
            else if(a[i]<b[j]){
                result[index] = a[i];
                i+=1;
            }else{
                result[index] = b[j];
                j+=1;
            }
            index+=1;
        }
        return result;
    }
    public static int[] mergeArr(int l,int mid,int r,int[] arr){
        int[] temp = Arrays.copyOfRange(arr,l,r+1);
        int i=l;
        int j=mid;
        for(int k=l;k<=r;k++){
            if(i==mid){
                arr[k] = temp[j-l];
                j++;
            }else if(j==r+1){
                arr[k] = temp[i-l];
                i++;
            }else if(temp[i-l]>temp[j-l]){
                arr[k] = temp[j-l];
                j++;
            }else{
                arr[k] = temp[i-l];
                i++;
            }
        }
        return arr;
    }
     public static void swap(int a,int b,int[] arr){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
